#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        if (needle.empty())
        {
            return 0;
        }
        return kmp(haystack, needle);
    }
    int kmp(string origin, string target)
    {
        int n = target.size();
        if (n == 0)
            return 0;
        vector<int> next(n, 0);
        for (int i = 1, j = 0; i < n; ++i)
        {
            while (j > 0 && target[i] != target[j])
                j = next[j - 1];
            if (target[i] == target[j])
                j++;
            next[i] = j;
        }

        for (int i = 0, j = 0; i < origin.size(); ++i)
        {
            while (j > 0 && origin[i] != target[j])
            {
                j = next[j - 1];
            }
            if (origin[i] == target[j])
                j++;
            if (j == n)
                return i - n + 1;
        }
        return -1;
    }
};